package Offer;
//剑指offer07.重建二叉树
public class Offer7 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = __buildTree(preorder,inorder);
        return root;
    }
    public TreeNode __buildTree(int[] preorder,int[] inorder){
        //preorder的长度和inorder的长度永远相等
        if(preorder.length==0)
            return null;
        int i = 0;//指向preorder
        int j = 0;//指向inorder
        TreeNode root = new TreeNode(preorder[i]);
        //如果数组里只有一个数字，说明应该直接返回这个根节点
        if(preorder.length==1)
            return root;
        //首先在inorder中找到根节点
        while(inorder[j]!=preorder[i])j++;
        //inorder中，在j左边的都是左子树，在j右边的都是右子树
        //递归搞定左右子树
        if(j!=0){
            int[] pre = new int[j];int[] in = new int[j];
            System.arraycopy(preorder,1,pre,0,j);
            System.arraycopy(inorder,0,in,0,j);
            root.left = __buildTree(pre,in);
        }
        if(preorder.length-j != 0){
            int[] pre = new int[preorder.length-j-1];int[] in = new int[inorder.length-j-1];
            System.arraycopy(preorder,j+1,pre,0,preorder.length-j-1);
            System.arraycopy(inorder,j+1,in,0,inorder.length-j-1);
            root.right=__buildTree(pre,in);
        }
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        Offer7 offer = new Offer7();
        offer.buildTree(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7});
    }

}
